#include <stdio.h>
#include <stdlib.h>

#define kMaxSize 10
#define NILL -1 /* 假设数据为非负整数，NIL定义为非法数据，表示空 */
typedef int TElemSet;

typedef struct BinaryTreeNode *BinaryTree;
struct BinaryTreeNode {
    TElemSet data; /* 数据元素 */
    BinaryTree left; /* 左孩子指针 */
    BinaryTree right; /* 右孩子指针 */
};

/* 链式队列定义 */
typedef enum {false, true} bool;
typedef BinaryTree QElemSet;
#define NIL NULL

typedef struct QueueNode *Position; /* 指针即结点位置 */
struct QueueNode {
    QElemSet data; /* 存储数据 */
    Position next; /* 链接队列中下一个元素的位置 */
};
typedef struct QueueHeadNode *Queue;
struct QueueHeadNode {
    int size; /* 链接队列中当前元素个数 */
    Position front; /* 链接队列的队首指针，初始化为NULL */
    Position rear; /* 链接队列的队尾指针，初始化为NULL */
};

void InitQueue(Queue queue) {
    /* 初始化一个空的链接队列 */
    queue->size = 0;
    queue->front = NULL;
    queue->rear = NULL;
}

bool IsEmpty(Queue queue) {
    /* 判断队列是否为空 */
    if (queue->size == 0)
        return true;
    else
        return false;
}

void EnQueue(Queue queue, QElemSet x) {
    Position new_node;

    new_node = (Position)malloc(sizeof(struct QueueNode));
    new_node->data = x;
    new_node->next = NULL;
    if (IsEmpty(queue)) { /* 特殊处理插入空队列的情况 */
        queue->rear = new_node;
        queue->front = new_node;
    } else {
        queue->rear->next = new_node;
        queue->rear = queue->rear->next;
    }
    queue->size++;
}

QElemSet GetFront(Queue queue) {
    if (IsEmpty(queue)) {
        printf("错误：队列为空。\n");
        return NIL;
    } else {
        return queue->front->data;
    }
}

void DeQueue(Queue queue) {
    Position temp;

    if (IsEmpty(queue)) {
        printf("错误：队列为空。\n");
    } else {
        temp = queue->front;
        queue->front = queue->front->next;
        free(temp);
        queue->size--;
        if (queue->front == NULL) {
            /* 特殊处理删除后变为空的队列 */
            queue->rear = NULL;
        }
    }
}

void DestroyQueue(Queue queue) {
    free(queue);
}
/* 队列定义结束*/

BinaryTree CreateBinaryTree(TElemSet value, BinaryTree left_tree,
                            BinaryTree right_tree) {
    BinaryTree tree;

    tree = (BinaryTree)malloc(sizeof(struct BinaryTreeNode));
    tree->data = value;
    tree->left = left_tree;
    tree->right = right_tree;
    return tree;
}

void Visit(BinaryTree tree) {
    printf("%d\n", tree->data);
}

void LevelOrder(BinaryTree tree) {
    Queue queue;
    BinaryTree node_ptr;

    queue = (Queue)malloc(sizeof(struct QueueHeadNode));
    InitQueue(queue); /* 初始化队列queue，用于存放结点 */
    EnQueue(queue, tree); /* 树根结点入队 */
    while (IsEmpty(queue) == false) {
        node_ptr = GetFront(queue); /* 取出队首结点 */
        DeQueue(queue);
        if (node_ptr != NULL) { /* 结点非空 */
            Visit(node_ptr); /* 访问结点 */
            EnQueue(queue, node_ptr->left); /* 左子结点入队 */
            EnQueue(queue, node_ptr->right);/* 右子结点入队 */
        }
    }
    DestroyQueue(queue);
}

/* 算法5-14：根据层序序列重构二叉树 LevelOrderDeSerialize(levelorder, n) */
BinaryTree LevelOrderDeSerialize(TElemSet levelorder[], int n) {
    Queue queue;
    BinaryTree tree, node_ptr;
    TElemSet data;
    int k;

    if (n == 1) { /* 序列中只有一个# */
        tree = NULL; /* 空树 */
    } else {
        queue = (Queue)malloc(sizeof(struct QueueHeadNode));
        InitQueue(queue);
        tree = (BinaryTree)malloc(sizeof(struct
                                         BinaryTreeNode)); /* 创建树根结点 */
        tree->data = levelorder[0]; /* 代入线性表第一个元素 */
        EnQueue(queue, tree);
        k = 1;
        while (k < n) { /* 从线性表第二个位置开始读取 */
            node_ptr = GetFront(queue); /* 队首结点出队 */
            DeQueue(queue);
            data = levelorder[k]; /* 线性表第k+1个元素 */
            if (data != NILL) {
                node_ptr->left = (BinaryTree)malloc(sizeof(struct
                                                    BinaryTreeNode)); /* 生成左子结点 */
                node_ptr->left->data = data; /* 线性表第k+1个元素代入左子节点 */
                EnQueue(queue, node_ptr->left); /* 左子结点入队 */
            } else {
                node_ptr->left = NULL; /* 左子树设置为空树 */
            }
            k++;
            data = levelorder[k]; /* 线性表第k+2个元素 */
            if (data != NILL) {
                node_ptr->right = (BinaryTree)malloc(sizeof(struct
                                                     BinaryTreeNode)); /* 生成右子结点 */
                node_ptr->right->data = data; /* 线性表第k+2个元素代入右子节点 */
                EnQueue(queue, node_ptr->right); /* 右子结点入队 */
            } else {
                node_ptr->right = NULL; /* 右子树设置为空树 */
            }
            k++; /* k为下一个待处理的位置 */
        }
    }
    DestroyQueue(queue);
    return tree; /* 返回新建的二叉树 */
}
/* 算法5-14 结束 */

int main(void) {
    BinaryTree tree;
    TElemSet *levelorder;
    char s[kMaxSize];
    int n, i;

    scanf("%d\n", &n);
    levelorder = (TElemSet *)malloc(sizeof(TElemSet) * n);
    for (i = 0; i < n; i++) {
        scanf("%s ", s);
        if (s[0] == '#') {
            levelorder[i] = NILL;
        } else {
            levelorder[i] = atoi(s);
        }
    }
    tree = LevelOrderDeSerialize(levelorder, n);
    LevelOrder(tree);

    return 0;
}